package com.example.demo.algorithm.lesson.basic.class2;

import com.example.demo.algorithm.lesson.basic.domain.DoubleNode;
import com.example.demo.algorithm.lesson.basic.domain.LinkedListHelper;
import com.example.demo.algorithm.lesson.basic.domain.Node;

/**
 * @author liweizhi
 * @date 2020/4/23
 */
public class DeleteGivenValue {
    public static Node singlyDelete(Node head, int value) {
        while (head != null) {
            if (head.getValue() == value) {
                head = head.getNext();
            } else {
                break;
            }
        }
        Node cur = head;
        Node pre = cur;
        while (cur != null) {
            // 如果连续出现的话,就"跳级"
            if (cur.getValue() == value) {
                pre.setNext(cur.getNext());
            } else {
                pre = cur;
            }
            cur = cur.getNext();
        }
        return head;
    }

    public static DoubleNode doubleDelete(DoubleNode head, int value) {
        while (head != null) {
            if (head.getValue() == value) {
                head = head.getNext();
                head.setLast(null);
            } else {
                break;
            }
        }
        DoubleNode cur = head;
        DoubleNode pre = cur;
        while (cur != null) {
            // 如果连续出现的话,就"跳级"
            if (cur.getValue() == value) {
                pre.setNext(cur.getNext());
                cur.getNext().setLast(pre);
            } else {
                pre = cur;
            }
            cur = cur.getNext();
        }
        return head;
    }


    public static void main(String[] args) {
//        singlyDeleteTest();
        doubleDeleteTest();
    }

    private static void singlyDeleteTest() {
        Node node = new Node(10);
        node.setNext(new Node(10));
        node.getNext().setNext(new Node(10));
        node.getNext().getNext().setNext(new Node(2));
        Node n = new Node(9);
        n.setNext(node);
        LinkedListHelper.printLinkedList(n);
        Node ret = singlyDelete(node, node.getNext().getValue());
        LinkedListHelper.printLinkedList(ret);
    }

    private static void doubleDeleteTest() {
        DoubleNode n1 = new DoubleNode(10);
        DoubleNode n2 = new DoubleNode(1);
        DoubleNode n3 = new DoubleNode(10);
        DoubleNode n4 = new DoubleNode(10);
        DoubleNode n5 = new DoubleNode(2);
        n1.setNext(n2);
        n2.setLast(n1);

        n2.setNext(n3);
        n3.setLast(n2);

        n3.setNext(n4);
        n4.setLast(n3);

        n4.setNext(n5);
        n5.setLast(n4);

        LinkedListHelper.printLinkedList(n1);
        DoubleNode ret = doubleDelete(n1, 10);
        LinkedListHelper.printLinkedList(ret);
    }
}
